package selectionSort

import (
	mySort "algorithms/interface/sort"
	"golang.org/x/exp/constraints"
	"sort"
)

/*选择排序：每次选择无序部分arr[i:n]的最小值arr[j]，和有序部分arr[0:i]的arr[i]交换*/

// Sort 选择排序法
// 顺序排序，从小到大
func Sort[E mySort.Comparable[E]](arr []E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i; j < len(arr); j++ {
			if arr[j].CompareTo(arr[minIndex]) < 0 {
				minIndex = j
			}
		}
		swap(arr, i, minIndex)
	}
}

// Sort0 选择排序法
// 顺序排序，从小到大
// 需实现sort.Interface接口，才能进行排序
func Sort0[E sort.Interface](arr E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < arr.Len(); i++ {
		minIndex := i
		for j := i; j < arr.Len(); j++ {
			if arr.Less(j, minIndex) {
				minIndex = j
			}
		}
		arr.Swap(i, minIndex)
	}
}

// Sort2 选择排序法
// 顺序排序，从小到大
// 仅支持基础类型排序
func Sort2[E constraints.Ordered](arr []E) {
	//arr[i:n]是有序的，arr[0:i]是无序的
	//循环不变量，未排序部分
	for i := len(arr) - 1; i >= 0; i-- {
		maxIndex := i
		for j := i; j >= 0; j-- {
			if arr[j] > arr[maxIndex] {
				maxIndex = j
			}
		}
		swap(arr, i, maxIndex)
	}
}

// Sort1 选择排序法
// 顺序排序，从小到大
// 仅支持基础类型排序
func Sort1[E constraints.Ordered](arr []E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		swap(arr, i, minIndex)
	}
}

func swap[E any](arr []E, i, j int) {
	tem := arr[i]
	arr[i] = arr[j]
	arr[j] = tem
}
